The present invention relates to locating errors in interleaved code words, and particularly to a system and method for providing additional error locating capability with relatively little overhead.
Existing data storage devices, such as disk drives, utilize Reed-Solomon error correcting codes to perform burst error correction and to achieve higher storage densities. The capability to correct multiple error bursts in near real time is necessary to minimize error recovery time and avoid the interruption of data flow.
Because magnetic data storage devices tend to generate errors in bursts, data stored on magnetic storage devices is typically arranged in an interleaved format. Interleaving is often used to spread the consecutive error bits or symbols into different interleaves which can each be corrected individually. Because interleaving allows the same hardware decoder core to process multiple interleaves repeatedly, interleaving is a cost effective technique to effectively combat burst errors.
Conventional interleaved coding techniques, however, are not without their shortcomings. For instance, interleaved code words have the same number of redundant check symbols and thus possess the same error correction capability. It has been observed that random errors may concentrate in one or two interleaves instead of substantially all interleaves. This concentration of random errors serves to defeat the effectiveness of providing redundant check symbols in each interleaved code word. Concerning long burst errors, a correlation exists between error locations in different interleaved code words. If all of the burst error locations can be identified and marked as erasures for the interleaved code words, error and erasure decoding can more successfully correct interleaved code words. Based upon the foregoing, there exists a need for a system and method for efficiently providing an error locating coding scheme that is tailored to locate errors typically encountered in a magnetic storage medium.
The present invention overcomes the shortcomings in prior systems and thereby satisfies a significant need for a system and method for efficiently locating errors in interleaved code words stored in a storage device. The system selectively provides additional check symbols to increase the power of uncorrectable interleaved code words without a substantial increase in overhead.
Conventional interleaved code words may be viewed as row codes wherein each interleaved code word includes a plurality of information symbols and a plurality of check symbols. In the preferred embodiments of the present invention, an error locating code word is created from selected columns of each interleaved code word. The error locating code word is stored with the corresponding interleaved code words in memory. The error locating code word is created in part by utilizing the same Reed-Solomon generator polynomial that is used in the formation of the interleaved code words.
The preferred embodiments of the present invention include software and hardware necessary for initially scrambling the symbols from the selected columns of the interleaved code words and creating column parity check symbols from the scrambled symbols. Each column parity check symbol, created using an operator such as an exclusive-OR boolean operator, is as wide as the width of a symbol extracted from the interleaved code word. The system software and hardware performs an operation on the high and low nibbles of each column parity check symbol to generate a plurality of reduced column parity check symbols, wherein each reduced column parity check symbol has a width that is half the width of each column parity check symbol. The software and hardware merges together pairs of the reduced column parity check symbols corresponding to two separate columns of the interleaved code words to create a plurality of merged column check symbols. The encoding operation is complete upon performing a Reed-Solomon encoding operation on the merged column check symbols to create error locating check symbols. The error locating code word is formed from the merged column check symbols and the error locating check symbols
Following retrieval of the interleaved code words and corresponding error locating check symbols from the storage device, the merged column check symbols are reconstructed from the symbols of the selected columns of the retrieved interleaved code words using the same encoding procedure used to generate the error locating code word. At around the same time the interleaved code words are decoded, the reconstructed merged column check symbols are used to compute the partial syndromes of the error locating code word. Upon the affirmative determination of the presence of error locations and patterns in a decoded interleaved code word, the partial syndromes of the error locating code word are modified accordingly.
The system software and hardware decodes the error locating code word upon the affirmative determination of any uncorrectable interleaved code words. A Reed-Solomon decoding operation is used to decode the error locating code word. Noting that a merged column check symbol corresponds to two selected columns in the interleaved code words, the column of the interleaved code word is identified for each error in the decoded error locating code word. The symbols in the identified columns of the previously uncorrectable interleaved code words are then marked as erasures. Error and erasure decoding of the uncorrectable interleaved code words is then performed a second time.